Exercise: Sorting Algorithms
Implement an updated version of the merge-sort algorithm.
We'll cover the following
Task#
Implement a version of the merge-sort algorithm that sorts a DLList without using an auxiliary array.
Sample input
The sample input will be as follows:
5 2 9 1 3 6
Expected output
The expected output will be as follows:
Original List: 5 2 9 1 3 6
Sorted List: 1 2 3 5 6 9
Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.
Good luck!
Note: You must implement the method
add(),merge_sort(),_merge_sort(Node head), and_merge(Node left, Node right)in the below code starting at line 12.
Implementation of merge-sort using DLList
Discussion on Sorting Algorithms
Solution: Sorting Algorithms